package 递归回溯.二维版;

import java.util.ArrayDeque;
import java.util.Deque;

public class No79单词搜索 {

    /**
     * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
     * 同一个单元格内的字母不允许被重复使用。
     *
     * 示例:
     * board =
     * [
     *   ['A','B','C','E'],
     *   ['S','F','C','S'],
     *   ['A','D','E','E']
     * ]
     * 给定 word = "ABCCED", 返回 true
     * 给定 word = "SEE", 返回 true
     * 给定 word = "ABCB", 返回 false
     */

    private char[][] arr;
    private int allLength;
    private int itemLength;
    private boolean[][] flag;
    //向上移 向右移 向下移 向左移
    private int[][] d={{-1,0},{0,1},{1,0},{0,-1}};

    int count;

    public boolean exist(char[][] board, String word) {
        /**
         * 上右下左依次遍历 ↑ → ↓ ← 依次遍历
         */
        //每个一维数组长度必定都一样
        this.itemLength =board[0].length;
        this.allLength =board.length;
        this.flag=new boolean[board.length][board[0].length];
        this.arr=board;

        /**
         * 第一步:遍历所有点,对每个点进行递归
         */
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                boolean result = dg(i, j, word, 0);
                //找到了才返回true
                if(result)
                    return true;
            }
        }

        //遍历完,没找到就返回false
        return false;
    }

    private boolean dg(int startX,int startY,String word,int index){

        /**
         * 第二步:分析各种情况
         * 1.到终点了,并且终点的元素等于目标字符串的最后一个就返回true
         * 2.没到终点,但是当前字符等于目标字符串中对应字符,就上左下右寻找,找到了立马返回true
         * 3.没到终点,但是当前字符不等于目标字符串中对应字符,就直接return
         */

        if(index==word.length()-1)
            return arr[startX][startY]==word.charAt(index);

        if(arr[startX][startY]==word.charAt(index)){
            //设置足迹
            flag[startX][startY]=true;
            count++;
            //上左下右 四个方向
            /**
             * 快捷写法:定义好一个方向数组,然后for4次
             */
            for (int i = 0; i < 4; i++) {
                int newX=startX+d[i][0];
                int newY=startY+d[i][1];
                //越界/之前已访问 就不去递归它
                if((newX<0||newX>= allLength ||newY<0||newY>= itemLength)||flag[newX][newY]){
                    //什么都不做,也别return,因为其他方向还要找
                }else{
                    boolean resultFlag = dg(newX, newY, word, index + 1);
                    /**
                     * 时刻记住,只要返回为true了,才不用继续找
                     */
                    if(resultFlag)
                        return true;
                }
            }
            //回溯
            flag[startX][startY]=false;
        }

        //上下左右都找了,但是没有符合的
        return false;
    }

    public static void main(String[] args) {
        No79单词搜索 n=new No79单词搜索();
        char[][] arr={{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        boolean flag = n.exist(arr, "ABCCED");
        System.out.println(flag);
        System.out.println(n.count);

        myNo79 m=new myNo79();
        boolean abcced = m.exist(arr, "ABCCED");
        System.out.println(abcced);
    }

}



/**
 * 我要自己再写一次
 */
class myNo79{

    private int itemLength;
    private int allLength;
    private char[][] arr;
    private boolean[][] flag;
    //上 右 下 左
    private int[][] coordinate={{-1,0},{0,1},{1,0},{0,-1}};

    public boolean exist(char[][] board, String word){
        this.allLength=board.length;
        this.itemLength=board[0].length;
        this.arr=board;
        this.flag=new boolean[allLength][itemLength];
        Deque<Character> list=new ArrayDeque<>(word.length());
        for (int i = 0; i < word.length(); i++) {
            list.addLast(word.charAt(i));
        }

        //每个点都需要遍历一次进行递归
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                boolean result = dg(i, j, list);
                if(result)
                    return true;
            }
        }

        return false;
    }

    private boolean dg(int startX,int startY,Deque<Character> list){

        if(list.size()==1&&list.getFirst()==arr[startX][startY])
            return true;//只剩最后一个,且也相等了

        //当前元素相等才进行上右下左的寻找
        if(arr[startX][startY]==list.getFirst()){
            Character removeFirst = list.removeFirst();
            flag[startX][startY]=true;
            //开始寻找四个方向
            for (int i = 0; i < 4; i++) {
                int newX=startX+coordinate[i][0];
                int newY=startY+coordinate[i][1];
                //不越界&&没搜寻过
                if(newX>=0&&newX<=allLength-1&&newY>=0&&newY<=itemLength-1&&!flag[newX][newY]){
                    //符合条件的才进行
                    boolean resultFlag = dg(newX, newY, list);
                    if(resultFlag)
                        return true;
                }
            }
            list.addFirst(removeFirst);
            flag[startX][startY]=false;
        }

        //当前元素不符合直接返回false
        return false;
    }

}
